/*
 * @Author: aponder
 * @Date: 2020-04-23 23:47:05
 * @LastEditors: aponder
 * @LastEditTime: 2020-04-23 23:52:06
 * @FilePath: /leetcode-zh/medium/面试题.08.11.硬币/Solution.java
 */
/*
 * @lc app=leetcode.cn lang=java
 *
 * 面试题 08.11. 硬币
 *
 * https://leetcode-cn.com/problems/coin-lcci
 *
 * algorithms
 * Medium (51.3%)
 * 
 * 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
 * 
 * 示例1:
 * 
 *  输入: n = 5
 *  输出：2
 *  解释: 有两种方式可以凑成总金额:
 * 5=5
 * 5=1+1+1+1+1
 * 示例2:
 * 
 *  输入: n = 10
 *  输出：4
 *  解释: 有四种方式可以凑成总金额:
 * 10=10
 * 10=5+5
 * 10=5+1+1+1+1+1
 * 10=1+1+1+1+1+1+1+1+1+1
 * 说明：
 * 
 * 注意:
 * 
 * 你可以假设：
 * 
 * 0 <= n (总金额) <= 1000000
 */

// @lc code=start
class Solution {
    public int waysToChange(int n) {
        // int[] coinTypes = new int[] { 1, 5, 10, 25 };
        // int[] coinNums = new int[] { n, 0, 0, 0 };
        // int count = 1;
        // for (int i = 0; i < coinTypes.length; i++) {
        //     while (coinNums[i] - coinTypes[i+1] > 0) {
        //         count++;
        //         coinNums[i] -= coinTypes[i+1];
        //         coinNums[i+1] += 1;
        //     }
        // }
        // return count;
        int mod = 1000000007;
        long count = 0;
        // n = 25a + 10b + 5c + d
        int a = n / 25;
        for (int i = 0; i <= a; i++) {
            int rest = n - 25 * i;
            long p = rest / 10;
            long q = rest / 5;
            // (q - p + 1) * (p + 1)
            count += (q - p + 1) * (p + 1);
            // long t = (q+1)*(p+1) % mod;
            // count += t;
            // t = p*(p+1) % mod;
            // count -= t;
            count %= mod;
        }
        return (int) count;
    }
}

// 5->2: 1@5; 5@1
// 10->4: 1@10; 1@5,5@1; 5@2; 10@1
// 25->: 1@25; 1@20,5@1; 1@15,5@2 
// @lc code=end

